/*
自己尝试了几次，通过不了所有的测试用例，于是看了题解

大致思路是通过从最高位到最低位逐位分析数字。k初始化为 1000000000，在每次循环中k不断除以 10，从而逐位处理数字n。
对于当前位 ans（通过n/k%10得到）
ans<2，那么这一位及更高位固定时，该位为 2 的数字个数就是低位数字的组合数sum乘以当前位的权重k。
ans==2，除了前面的情况，还要加上低位数字的个数（n%k + 1）。
ans>2，这一位及更高位固定时，该位为 2 的数字个数就是(sum + 1)*k。

LC面试题 17.06 2出现的次数
 难度：困难  2024.09.29
https://leetcode.cn/problems/number-of-2s-in-range-lcci/
*/


class Solution {
public:
    long k = 1000000000;
    int numberOf2sInRange(int n) {
        if(n<=1)return 0;
        if(n<=11)return 1;
        int count = 0, sum = 0;
        while (k > 0) {
            int ans = n / k % 10;
            if (ans < 2) {
                count += sum * k;
            } else if (ans == 2) {
                count += sum * k + n % k + 1;
            } else {
                count += (sum + 1) * k;
            }
            k /= 10;
            sum = sum * 10 + ans;
        }
        return count;
    }
};